package 程序员面试金典;

/**
 * 面试题 04.10. 检查子树
 * 检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
 *
 * 如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。
 *
 * 注意：此题相对书上原题略有改动。
 *
 * 示例1:
 *
 *  输入：t1 = [1, 2, 3], t2 = [2]
 *  输出：true
 * 示例2:
 *
 *  输入：t1 = [1, null, 2, 4], t2 = [3, 2]
 *  输出：false
 * 提示：
 *
 * 树的节点数目范围为[0, 20000]。
 */
public class T04_10 {
    //使用双重深度递归遍历 第一层 是为了找到 相同的根节点 ， 然后从根节点 进入第二重深度遍历 判断是否存在不一致的叶子节点
    private boolean ans = false;

    public boolean checkSubTree(TreeNode t1, TreeNode t2) {

        if (t1 == null) {
            return false;
        }

        if (t1.val == t2.val) {
            ans = ans || dfs(t1, t2);
        } else {
            checkSubTree(t1.left, t2);
            checkSubTree(t1.right, t2);
        }

        return ans;

    }

    public boolean dfs(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null && root2 != null) {
            return false;
        }
        if (root1 != null && root2 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return dfs(root1.left, root2.left) && dfs(root1.right, root2.right);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
